package cn.edu.gzu.nonlinear_time.swap;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 西瓜不怕冷
 * 排序算法之冒泡排序
 * 愿与诸君共同学习
 * 源https://zhuanlan.zhihu.com/p/122452652
 */
public class BubbleSortTest {
    /*
       冒泡排序
       最基础的 非线性时间的 稳定 交换 排序算法
       1、冒泡排序是原地排序算法
        因为冒泡排序过程中并不需要开辟新的数组空间，只需要常数个变量用于标记或者交换，所以冒泡排序是原地排序算法。
        空间复杂度显然是O(1)

       2、冒泡排序是稳定排序算法
        在比较交换操作过程中，如果第一个元素大于第二个元素，我们才交换两个元素，两个元素相等时，保持不变。
        所以两个相等的元素在排序前后的相对位置并不会发生变化，所以冒泡排序是稳定排序算法。

       3、时间复杂度是O(n2)
       最好情况
        此时数组本身已经有序，冒泡排序只需要一轮就可退出，时间复杂度为O(n)

       最坏情况
        此时数组本身是逆序的，完成冒泡排序需要n轮，比较的次数为n+(n-1)+(n-2)+...+2+1，时间复杂度为O(n2)

       平均情况
        鉴于对最坏情况下的时间复杂度分析，得出平均情况下的时间复杂度为O(n2)
     */


    /**
     * 记录冒泡排序的轮数
     */
    private static int number = 0;
    private static final int[] ARRAY = new int[]{5, 3, 6, 2, 1, 4, 8, 7};
    /**
     * 代码如下 基础实现
     */
    @Test
    public void bubbleSort() {
        for (int i = 0; i < ARRAY.length; i++) {
            //表示是否发生交换操作，每轮结束后置为false
            for (int j = 0; j < ARRAY.length - i - 1; j++) {
                //比较交换
                if (ARRAY[j] > ARRAY[j + 1]) {
                    int temp = ARRAY[j];
                    ARRAY[j] = ARRAY[j + 1];
                    ARRAY[j + 1] = temp;
                }
            }
            number++;
        }
        System.out.println(Arrays.toString(ARRAY));
        System.out.println("共经过" + number + "轮冒泡排序");
        // 结果是8轮询环
    }

    //优化版本1

    /**
     * 回顾上面的案例，可以发现实际上第四轮结束后，数组已经是有序的，所以后面的每轮冒泡都只有比较操作而没有交换操作了。
     * 这是因为前面的每轮冒泡不仅会确定一个最大的元素放在最右侧，还会使得较大的元素往右侧移动，
     * 所以冒泡排序通常会提前几轮就能达到有序（除非数组是完全逆序的。
     * 优化点：如果在某轮排序中，没有发生交换操作，说明数组已经有序，可提前退出排序。
     */
    @Test
    public void bubbleSortPlus() {
        //表示是否发生交换操作，每轮结束后置为false
        for (int i = 0; i < ARRAY.length; i++) {
            boolean isOccurExchange = false;
            for (int j = 0; j < ARRAY.length - i - 1; j++) {
                //比较交换
                if (ARRAY[j] > ARRAY[j + 1]) {
                    int temp = ARRAY[j];
                    ARRAY[j] = ARRAY[j + 1];
                    ARRAY[j + 1] = temp;
                    isOccurExchange = true;
                }
            }
            number++;
            //说明这轮没有发生元素交换，数组已经有序
            if (!isOccurExchange) {
                break;
            }
        }
        System.out.println(Arrays.toString(ARRAY));
        System.out.println("共经过" + number + "轮冒泡排序");
        // 结果是5轮询环
    }

    /*
      尚可优化，未完待续
     */
}
